/**
 * @file     searchRange.ts
 * @brief    [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
 * @author   Zhu
 * @date     2022-11-14 09:12
 */

// 递归
function searchRange(nums: number[], target: number): number[] {
    /**
     * 二分搜索第一个或最后一个出现的值
     * @param left 左下标
     * @param right 右下标
     * @param pickFirst 找到第一个还是最后一个
     * @returns 目标值索引
     */
    function binarySearch(left: number, right: number, pickFirst = false) {
        if (left > right) return -1;
        if (left === right) return nums[left] === target ? left : -1;
        const midFunc = pickFirst ? Math.floor : Math.ceil;
        let mid = midFunc((right - left) / 2) + left;

        if (nums[mid] === target) {
            if (pickFirst) {
                return binarySearch(left, mid, pickFirst);
            } else {
                return binarySearch(mid, right, pickFirst);
            }
        } else if (nums[mid] < target) {
            return binarySearch(mid + 1, right, pickFirst);
        } else {
            return binarySearch(left, mid - 1, pickFirst);
        }
    }

    const first = binarySearch(0, nums.length - 1, true);
    const last = binarySearch(0, nums.length - 1, false);

    return [first, last];
}

// 迭代
function searchRange(nums: number[], target: number): number[] {
    function binarySearch(left: number, right: number, pickFirst = false) {
        const midFunc = pickFirst ? Math.floor : Math.ceil;

        while (left < right) {
            let mid = midFunc((right - left) / 2) + left;
            if (nums[mid] === target) {
                if (pickFirst) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left] === target ? left : -1;
    }

    const first = binarySearch(0, nums.length - 1, true);
    const last = binarySearch(0, nums.length - 1, false);

    return [first, last];
}

// 2024-11-27 10:47:00
function searchRange(nums: number[], target: number): number[] {
    const n = nums.length;
    function binarySearch(pickLeft = true) {
        let left = 0,
            right = n - 1;
        while (left < right) {
            const mid = ((left + right) >> 1) + (pickLeft ? 0 : 1); // mid offset
            if (nums[mid] === target) {
                if (pickLeft) {
                    // limit move
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left] === target ? left : -1;
    }

    const first = binarySearch(true);
    const last = binarySearch(false);

    return [first, last];
}
